package 贪心算法.买卖股票最佳时机;

import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/4/13 20:55
 *  prices[] ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
 * @description: 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        int i = maxProfit3(prices);
        System.out.println(i);
    }

    //解法1 超出内存限制，不可取
    public static int maxProfit(int[] prices) {
        List<Integer> list = new LinkedList<>();
        for (int i = prices.length -1; i >= 0 ; i--) {
            int n = prices[i];
            for (int j = 0; j <= i - 1; j++) {
              int tem = n - prices[j];
              if (tem > 0){
                  list.add(tem);
              }
            }
        }
        if (list.size() == 0){
            return 0;
        }
        Integer max = Collections.max(list);
        System.out.println(max);
        return max;
    }

    //解法1 超出内存限制，不可取
    public static int maxProfit4(int[] prices) {
        int max = 0;
        for (int i = prices.length -1; i >= 0 ; i--) {
            int n = prices[i];
            for (int j = 0; j <= i - 1; j++) {
                int tem = n - prices[j];
                if (tem > max){
                    max = tem;
                }
            }
        }
        System.out.println(max);
        return max;
    }



    //解法2单调栈
    public static int maxProfit2(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        Deque<Integer> deque = new LinkedList<>();
        int base = 0;
        int res = 0;
        for (int i = 0; i <= len; i++) {
            int curValue = i == len ? 0 : prices[i];
            while (!deque.isEmpty() && deque.peekLast() > curValue) {
                int top = deque.pollLast();
                res = Math.max(res, top - base);
            }
            if (deque.isEmpty()) {
                base = curValue;
            }
            deque.offerLast(curValue);
        }
        return res;
    }

    //动态规划 牛逼！！！
    public static int maxProfit3(int[] prices) {
        int len = prices.length;
        // 特殊判断
        if (len < 2) {
            return 0;
        }
        int[][] dp = new int[len][2];

        // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
        // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数

        // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 从第 2 天开始遍历
        for (int i = 1; i < len; i++) {
            //当天不持股的两种情况 1.前一天也没有持股 2 前一天持股当天卖掉
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            //当天持股的两种情况 1 前一天也持股 2 前一天不持股，当天买入
            dp[i][1] = Math.max(dp[i - 1][1], 0-prices[i]);
        }
        return dp[len - 1][0];
    }


}
